{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Burst Balloons"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxCoins"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #戳气球"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>有 <code>n</code> 个气球，编号为<code>0</code> 到 <code>n - 1</code>，每个气球上都标有一个数字，这些数字存在数组&nbsp;<code>nums</code>&nbsp;中。</p>\n",
    "\n",
    "<p>现在要求你戳破所有的气球。戳破第 <code>i</code> 个气球，你可以获得&nbsp;<code>nums[i - 1] * nums[i] * nums[i + 1]</code> 枚硬币。&nbsp;这里的 <code>i - 1</code> 和 <code>i + 1</code> 代表和&nbsp;<code>i</code>&nbsp;相邻的两个气球的序号。如果 <code>i - 1</code>或 <code>i + 1</code> 超出了数组的边界，那么就当它是一个数字为 <code>1</code> 的气球。</p>\n",
    "\n",
    "<p>求所能获得硬币的最大数量。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "<strong>示例 1：</strong>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [3,1,5,8]\n",
    "<strong>输出：</strong>167\n",
    "<strong>解释：</strong>\n",
    "nums = [3,1,5,8] --&gt; [3,5,8] --&gt; [3,8] --&gt; [8] --&gt; []\n",
    "coins =  3*1*5    +   3*5*8   +  1*3*8  + 1*8*1 = 167</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,5]\n",
    "<strong>输出：</strong>10\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == nums.length</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 300</code></li>\n",
    "\t<li><code>0 &lt;= nums[i] &lt;= 100</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [burst-balloons](https://leetcode.cn/problems/burst-balloons/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [burst-balloons](https://leetcode.cn/problems/burst-balloons/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[3,1,5,8]', '[1,5]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCoins(self, nums: List[int]) -> int:\n",
    "        nums = [1] + nums + [1]\n",
    "        dp = [[0] * len(nums) for _ in range(len(nums))]\n",
    "        def fun(begin, end):\n",
    "            tmp = 0\n",
    "            for pos in range(begin + 1, end):\n",
    "                tmp = max(tmp, dp[begin][pos] + nums[begin] * nums[pos] * nums[end] + dp[pos][end])\n",
    "            return tmp\n",
    "        for l in range(2, len(nums)):\n",
    "            for begin in range(len(nums) - l):\n",
    "                dp[begin][begin + l] = fun(begin, begin + l)\n",
    "        return dp[0][-1]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCoins(self, nums: List[int]) -> int:\n",
    "\n",
    "        n = len(nums)\n",
    "        nums = [1] + nums + [1]\n",
    "        dp = [[0 for _ in range(n+2)] for _ in range(n+2)]\n",
    "\n",
    "        for len_ in range(3, n+2+1):\n",
    "            for l in range(n+2-len_+1): # l+ len_ -1 < n+2\n",
    "                r = l + len_ -1\n",
    "                for k in range(l+1,r):\n",
    "                    '''假设在 (l,r) 范围内最后剩下的气球的编号为 k'''\n",
    "                    # dp[l][r] = max(dp[l][r], dp[l][k] + nums[k-1]*nums[k]*nums[k+1] + dp[k][r])\n",
    "                    dp[l][r] = max(dp[l][r], dp[l][k] + nums[l]*nums[k]*nums[r] + dp[k][r])\n",
    "\n",
    "        return dp[0][n+1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxCoins(self, nums: list[int]) -> int:\n",
    "        n = len(nums)        \n",
    "        nums = [1] + nums + [1]\n",
    "        \n",
    "        dp = [[0] * (n + 2) for _ in range(n + 2)]\n",
    "\n",
    "        for i in range(1, n+1):\n",
    "            dp[i][i] = nums[i-1] * nums[i] * nums[i+1]\n",
    "        for length in range(2, n+1):\n",
    "            for i in range(1, n+2-length):\n",
    "                j = i + length - 1\n",
    "                for k in range(i, j+1):\n",
    "                    dp[i][j] = max(dp[i][j], dp[i][k-1] + nums[i-1] * nums[k] * nums[j+1] + dp[k+1][j])\n",
    "        \n",
    "        return dp[1][n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCoins(self, nums: List[int]) -> int:\n",
    "        if len(nums) == 0:\n",
    "            return 0\n",
    "        if len(nums) < 2:\n",
    "            return nums[0]\n",
    "        nums = [1] + nums + [1]\n",
    "        dp = [[0] * len(nums) for _ in range(len(nums))]\n",
    "        for i in range(len(nums) - 1, -1, -1):\n",
    "            for j in range(i + 2, len(nums)):\n",
    "                for k in range(i + 1, j):\n",
    "                    dp[i][j] = max(dp[i][j], dp[i][k] + dp[k][j] + nums[i] * nums[k] * nums[j])\n",
    "        # print(dp)\n",
    "        return dp[0][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCoins(self, nums: List[int]) -> int:\n",
    "        nums.insert(0,1)\n",
    "        nums.insert(len(nums),1)\n",
    "        store = [[0]*(len(nums)) for i in range(len(nums))]\n",
    "        def range_best(i,j):\n",
    "            m = 0 \n",
    "            for k in range(i+1,j): \n",
    "                left = store[i][k]\n",
    "                right = store[k][j]\n",
    "                a = left + nums[i]*nums[k]*nums[j] + right\n",
    "                if a > m:\n",
    "                    m = a\n",
    "            store[i][j] = m\n",
    "        for n in range(2,len(nums)):\n",
    "            for i in range(0,len(nums)-n):\n",
    "                range_best(i,i+n)\n",
    "        return store[0][len(nums)-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCoins(self, nums: List[int]) -> int:\n",
    "        nums = [1] + nums + [1]\n",
    "        # 左右都闭区间\n",
    "        dp = [[0 for j in range(len(nums))] for i in range(len(nums))]\n",
    "        for i in range(len(nums)-2, 0, -1):\n",
    "            for j in range(1, len(nums)-1):\n",
    "                if i > j:\n",
    "                    continue\n",
    "                elif i == j:\n",
    "                    dp[i][j] = nums[i] * nums[i-1] * nums[i+1]\n",
    "                else:\n",
    "                    for k in range(i, j+1):\n",
    "                        cur_val = nums[k]*nums[i-1]*nums[j+1]+dp[i][k-1]+dp[k+1][j]\n",
    "                        dp[i][j] = max(dp[i][j], cur_val)\n",
    "        return dp[1][len(nums)-2]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCoins(self, nums: List[int]) -> int:\n",
    "        nums.insert(0,1)\n",
    "        nums.append(1)\n",
    "        print(nums)\n",
    "\n",
    "        n=len(nums)\n",
    "\n",
    "        dp = [[0]*n for _ in range(n)]\n",
    "\n",
    "        for i in range(n-1,-1,-1):\n",
    "            for j in range(i+1,n):\n",
    "                \n",
    "                for k in range(i+1,j):\n",
    "                    dp[i][j]=max(dp[i][j],dp[i][k]+dp[k][j]+ nums[k]*nums[i]*nums[j])\n",
    "            print(i,dp[i])\n",
    "\n",
    "        return dp[0][n-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCoins(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        # 添加两侧的虚拟气球\n",
    "       \n",
    "        points = [1] + nums + [1]\n",
    "        # base case 已经都被初始化为 0\n",
    "        dp = [[0] * (n + 2) for _ in range(n + 2)]\n",
    "        # 开始状态转移\n",
    "        for i in range(n,-1,-1):\n",
    "            for j in range(i+1,n+2):\n",
    "                for k in range(i+1,j):\n",
    "                    dp[i][j] = max(dp[i][j],dp[i][k]+ points[i]*points[k]*points[j]+dp[k][j])\n",
    "        print(dp)\n",
    "        return dp[0][n+1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCoins(self, nums: List[int]) -> int:\n",
    "        dp = [[0]*(len(nums)+2) for _ in range(len(nums)+2)]\n",
    "        \n",
    "        n = len(nums)\n",
    "        nums = [1]+nums+[1]\n",
    "        for i in range(1,n+1):\n",
    "            dp[i][i] = nums[i-1]*nums[i]*nums[i+1]\n",
    "        for i in range(n-1,0,-1):\n",
    "            for j in range(i+1,n+1):\n",
    "                tem = nums[i-1]*nums[j+1]\n",
    "                for k in range(i,j+1):\n",
    "                    if k == i:\n",
    "                        dp[i][j] = max(dp[i][j],nums[k]*tem+dp[k+1][j])\n",
    "                    elif k == j:\n",
    "                        dp[i][j] = max(dp[i][j],nums[k]*tem+dp[i][k-1])\n",
    "                    else:\n",
    "                        dp[i][j] = max(dp[i][j],nums[k]*tem+dp[i][k-1]+dp[k+1][j])\n",
    "        print(dp)\n",
    "        return dp[1][n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCoins(self, nums: List[int]) -> int:\n",
    "        nums = [1] + nums + [1]\n",
    "        # 左右都闭区间\n",
    "        dp = [[0 for j in range(len(nums))] for i in range(len(nums))]\n",
    "        for i in range(len(nums)-2, 0, -1):\n",
    "            for j in range(1, len(nums)-1):\n",
    "                if i > j:\n",
    "                    continue\n",
    "                elif i == j:\n",
    "                    dp[i][j] = nums[i] * nums[i-1] * nums[i+1]\n",
    "                else:\n",
    "                    for k in range(i, j+1):\n",
    "                        cur_val = nums[k]*nums[i-1]*nums[j+1]+dp[i][k-1]+dp[k+1][j]\n",
    "                        dp[i][j] = max(dp[i][j], cur_val)\n",
    "        print(dp)\n",
    "        return dp[1][len(nums)-2]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCoins(self, nums: List[int]) -> int:\n",
    "        nums = [1] + nums + [1]\n",
    "        n = len(nums)\n",
    "        dp = [[0] * n for _ in range(n)]\n",
    "\n",
    "        def calculate(i: int, j: int) -> int:\n",
    "            if dp[i][j] or j == i + 1:\n",
    "                return dp[i][j]\n",
    "            coins = 0\n",
    "            for k in range(i + 1, j):\n",
    "                coins = max(coins, nums[i] * nums[k] * nums[j] + calculate(i, k) + calculate(k, j))\n",
    "            dp[i][j] = coins\n",
    "            return coins\n",
    "\n",
    "        return calculate(0, n - 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCoins(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        points = [1]\n",
    "        for num in nums:\n",
    "            points.append(num)\n",
    "        points.append(1)\n",
    "\n",
    "        memo = [[-1 for _ in range(0, n+2)] for _ in range(0, n+2)]\n",
    "\n",
    "        def dp(points, i, j):\n",
    "            if j - i <= 1:\n",
    "                return 0\n",
    "            if memo[i][j] != -1:\n",
    "                return memo[i][j]\n",
    "            res = 0\n",
    "            for k in range(i + 1, j):\n",
    "                res = max(res, dp(points, i, k) + points[i]*points[k]*points[j] + dp(points, k, j))\n",
    "            memo[i][j] = res\n",
    "            return res\n",
    "\n",
    "        return dp(points, 0, n+1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCoins(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        val = [1] + nums + [1]\n",
    "\n",
    "        Solve = [[None for _ in range(n + 3)] for _ in range(n + 3)]\n",
    "        def dfs(left, right):\n",
    "            if left >= right - 1:\n",
    "                return 0\n",
    "            \n",
    "            best = 0\n",
    "            for i in range(left + 1, right):\n",
    "                total = val[left] * val[i] * val[right]\n",
    "                leftNum, rightNum = None, None\n",
    "                if Solve[left][i] is not None:\n",
    "                    leftNum = Solve[left][i]\n",
    "                else:\n",
    "                    leftNum = dfs(left, i)\n",
    "                \n",
    "                if Solve[i][right] is not None:\n",
    "                    rightNum = Solve[i][right]\n",
    "                else:\n",
    "                    rightNum = dfs(i, right)\n",
    "                \n",
    "                total += leftNum + rightNum\n",
    "                \n",
    "                best = max(best, total)\n",
    "            \n",
    "            Solve[left][right] = best\n",
    "            return best            \n",
    "\n",
    "        return dfs(0, n+1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCoins(self, nums: List[int]) -> int:\n",
    "        if len(nums) == 1:\n",
    "            return nums[0]\n",
    "        val = [1]+nums+[1]\n",
    "        n = len(val)\n",
    "        solve = [[0]*n for _ in range(n)]\n",
    "        def sol(i,j):\n",
    "            if i>=j-1:\n",
    "                return 0\n",
    "            if solve[i][j]:\n",
    "                return solve[i][j]\n",
    "            for m in range(i+1,j):\n",
    "                solve[i][j] = max(solve[i][j], val[i]*val[j]*val[m]+sol(i, m)+sol(m, j))\n",
    "            return solve[i][j]\n",
    "        return sol(0, n-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCoins(self, nums: List[int]) -> int:\n",
    "        nums = [1] + nums + [1]\n",
    "        record = [[-1 for _ in nums] for _ in nums]\n",
    "        def dp(l, r):\n",
    "            record[l][r] = 0\n",
    "            for i in range(l + 1, r):\n",
    "                if record[l][i] == -1:\n",
    "                    dp(l, i)\n",
    "                if record[i][r] == -1:\n",
    "                    dp(i, r)\n",
    "                record[l][r] = max(record[l][i] + record[i][r] + nums[i] * nums[l] * nums[r], record[l][r])\n",
    "        \n",
    "        dp(0, len(nums) - 1)\n",
    "        return record[0][len(nums) - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCoins(self, nums: List[int]) -> int:\n",
    "        length = len(nums)\n",
    "        dp = [[-1]*length for i in range(length)]\n",
    "        nums.extend([1])\n",
    "        for i in range(length):\n",
    "            dp[i][i] = nums[i-1]*nums[i]*nums[i+1]\n",
    "        def coin(i,j):\n",
    "            if i>j:\n",
    "                return 0\n",
    "            if dp[i][j]!=-1:\n",
    "                return dp[i][j]\n",
    "            else:\n",
    "                max_num = 0\n",
    "                for n in range(i,j+1):\n",
    "                    max_num=max(max_num,coin(i,n-1)+coin(n+1,j)+nums[i-1]*nums[n]*nums[j+1])\n",
    "            dp[i][j] = max_num\n",
    "            return max_num\n",
    "        res = coin(0,length-1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    ## solution 1\n",
    "    # def maxCoins(self, nums: List[int]) -> int:\n",
    "    #     self.sectionBoundry2maxCoins = {}\n",
    "    #     nums = [1] + nums + [1]\n",
    "    #     return self.maxCoins_in_one_section(nums, 0, len(nums)-1)\n",
    "    \n",
    "    # def maxCoins_in_one_section(self, nums, left_idx, right_idx):\n",
    "    #     sectionBoundry = (left_idx, right_idx)\n",
    "    #     if sectionBoundry in self.sectionBoundry2maxCoins:\n",
    "    #         return self.sectionBoundry2maxCoins[sectionBoundry]\n",
    "\n",
    "    #     maxCoins = 0\n",
    "    #     for mid_idx in range(left_idx + 1, right_idx):\n",
    "    #         curCoins = nums[left_idx] * nums[mid_idx] * nums[right_idx]\n",
    "    #         midCoins = curCoins + \\\n",
    "    #             self.maxCoins_in_one_section(nums, left_idx, mid_idx) + \\\n",
    "    #             self.maxCoins_in_one_section(nums, mid_idx, right_idx)\n",
    "    #         maxCoins = max(maxCoins, midCoins)\n",
    "        \n",
    "    #     self.sectionBoundry2maxCoins[sectionBoundry] = maxCoins\n",
    "    #     return maxCoins\n",
    "\n",
    "    ## solution 2\n",
    "    def maxCoins(self, nums: List[int]) -> int:\n",
    "        self.sectionBoundry2maxCoins = {}\n",
    "        nums = [1] + nums + [1]\n",
    "\n",
    "        min_left_idx = 0\n",
    "        min_right_idx = 2   \n",
    "        max_right_idx = len(nums) - 1\n",
    "        max_left_idx = len(nums) - 3\n",
    "        maxCoins = 0\n",
    "\n",
    "        for right_idx in range(min_right_idx, max_right_idx+1):\n",
    "            for left_idx in range(right_idx-2, min_left_idx-1, -1):\n",
    "                sectionBoundry = (left_idx, right_idx)\n",
    "                sectionMaxCoins = 0\n",
    "                for mid_idx in range(left_idx + 1, right_idx):\n",
    "                    left_sectionBoundry = (left_idx, mid_idx)\n",
    "                    right_sectionBoundry = (mid_idx, right_idx)\n",
    "\n",
    "                    curCoins = nums[left_idx] * nums[mid_idx] * nums[right_idx]\n",
    "                    midCoins = curCoins + \\\n",
    "                        self.sectionBoundry2maxCoins.get(left_sectionBoundry, 0) + \\\n",
    "                        self.sectionBoundry2maxCoins.get(right_sectionBoundry, 0)\n",
    "\n",
    "                    sectionMaxCoins = max(sectionMaxCoins, midCoins)\n",
    "\n",
    "                maxCoins = max(maxCoins, sectionMaxCoins)\n",
    "                self.sectionBoundry2maxCoins[sectionBoundry] = sectionMaxCoins\n",
    "\n",
    "        # print('maxCoins = ', maxCoins)\n",
    "        # print('self.sectionBoundry2maxCoins[(min_left_idx, max_right_idx)] = ', \n",
    "        #     self.sectionBoundry2maxCoins[(min_left_idx, max_right_idx)])\n",
    "        # print('self.sectionBoundry2maxCoins = ', self.sectionBoundry2maxCoins)\n",
    "        # assert self.sectionxBoundry2maxCoins[(min_left_idx, max_right_idx)] == maxCoins\n",
    "\n",
    "        return maxCoins\n",
    "    \n",
    "    ## solution 3\n",
    "    def maxCoins(self, nums: List[int]) -> int:\n",
    "        nums = [1] + nums + [1]\n",
    "        n = len(nums)\n",
    "\n",
    "        min_left_idx = 0\n",
    "        min_right_idx = 2   \n",
    "        max_right_idx = n - 1\n",
    "        max_left_idx = n - 3\n",
    "        # maxCoins = 0\n",
    "\n",
    "        self.sectionBoundry2maxCoins = [[0] * (max_right_idx - min_right_idx + 1) \n",
    "            for _ in range(max_left_idx - min_left_idx + 1)]\n",
    "        \n",
    "        self.sectionBoundry2maxCoins = [[0] * n\n",
    "            for _ in range(n)]\n",
    "\n",
    "        for right_idx in range(min_right_idx, max_right_idx+1):\n",
    "            for left_idx in range(right_idx-2, min_left_idx-1, -1):\n",
    "                sectionMaxCoins = 0\n",
    "                for mid_idx in range(left_idx + 1, right_idx):\n",
    "                    curCoins = nums[left_idx] * nums[mid_idx] * nums[right_idx]\n",
    "                    midCoins = curCoins + \\\n",
    "                        self.sectionBoundry2maxCoins[left_idx][mid_idx] + \\\n",
    "                        self.sectionBoundry2maxCoins[mid_idx][right_idx]\n",
    "\n",
    "                    sectionMaxCoins = max(sectionMaxCoins, midCoins)\n",
    "\n",
    "                # maxCoins = max(maxCoins, sectionMaxCoins)\n",
    "                self.sectionBoundry2maxCoins[left_idx][right_idx] = sectionMaxCoins\n",
    "\n",
    "        # print('maxCoins = ', maxCoins)\n",
    "        # print('self.sectionBoundry2maxCoins[(min_left_idx, max_right_idx)] = ', \n",
    "        #     self.sectionBoundry2maxCoins[(min_left_idx, max_right_idx)])\n",
    "        # print('self.sectionBoundry2maxCoins = ', self.sectionBoundry2maxCoins)\n",
    "        # assert self.sectionxBoundry2maxCoins[(min_left_idx, max_right_idx)] == maxCoins\n",
    "\n",
    "        # return maxCoins\n",
    "        return self.sectionBoundry2maxCoins[min_left_idx][max_right_idx]\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCoins(self, nums: List[int]) -> int:\n",
    "        if not nums:\n",
    "            return 0\n",
    "        n=len(nums)\n",
    "        q=[1]\n",
    "        q.extend(nums)\n",
    "        q.append(1)\n",
    "        dp=[[-1 for _ in range(n+3)] for _ in range(n+3)]\n",
    "        def method(l,r):\n",
    "            if dp[l][r]!=-1:\n",
    "                return dp[l][r]\n",
    "            if l==r:\n",
    "                res=q[l-1]*q[l]*q[l+1]\n",
    "            else:\n",
    "                res=0\n",
    "                x,y=q[l-1]*q[l]*q[r+1],q[l-1]*q[r]*q[r+1]\n",
    "                res=max(res,method(l+1,r)+x,method(l,r-1)+y)\n",
    "                for i in range(l+1,r):\n",
    "                    k=q[l-1]*q[i]*q[r+1]\n",
    "                    res=max(res,k+method(l,i-1)+method(i+1,r))\n",
    "            dp[l][r]=res\n",
    "            return res\n",
    "        return method(1,n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCoins1(self, nums: List[int]) -> int:\n",
    "        nums.insert(0,1)\n",
    "        nums.insert(len(nums),1)\n",
    "\n",
    "        store=[[0]*len(nums) for i in range(len(nums))]\n",
    "\n",
    "        def range_best(i,j):\n",
    "            m=0\n",
    "            for k in range(i+1,j):\n",
    "                left=store[i][k]\n",
    "                right=store[k][j]\n",
    "\n",
    "                a=left+right+nums[i]*nums[k]*nums[j]\n",
    "                if a>m:\n",
    "                    m=a\n",
    "            store[i][j]=m\n",
    "\n",
    "        for n in range(2,len(nums)):\n",
    "            for i in range(0,len(nums)-n):\n",
    "                range_best(i,i+n)\n",
    "        return store[0][len(nums)-1]\n",
    "    def maxCoins2(self, nums: List[int]) -> int:\n",
    "        nums.insert(0,1)\n",
    "        nums.insert(len(nums),1)\n",
    "        n=len(nums)\n",
    "        dp=[[0]*(n+1) for _ in range(n+1)]\n",
    "\n",
    "        for l in range(2,len(nums)):\n",
    "            for i in range(0,len(nums)-l):\n",
    "                j=i+l\n",
    "                for k in range(i+1,j):\n",
    "                    dp[i][j]=max(dp[i][k]+dp[k][j]+nums[i]*nums[k]*nums[j],dp[i][j])\n",
    "        #print(dp)\n",
    "        return dp[0][-2]\n",
    "    def maxCoins(self, nums: List[int]) -> int:\n",
    "        nums.insert(0,1)\n",
    "        nums.insert(len(nums),1)\n",
    "        n=len(nums)\n",
    "        dp=[[-1]*(n+1) for _ in range(n+1)]\n",
    "\n",
    "        def dfs(i,j):\n",
    "            if j-i<=1:\n",
    "                dp[i][j]=0\n",
    "                return 0\n",
    "            if dp[i][j]!=-1:\n",
    "                return dp[i][j]\n",
    "            for k in range(i+1,j):\n",
    "                tmp=dfs(i,k)+dfs(k,j)+nums[i]*nums[k]*nums[j]\n",
    "                dp[i][j]=max(dp[i][j],tmp)\n",
    "            return dp[i][j]\n",
    "        return dfs(0,len(nums)-1)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCoins(self, nums: List[int]) -> int:\n",
    "        #在原数组左右两边填充一个1，防止越界\n",
    "        val=[1]+nums+[1]\n",
    "        n=len(val)\n",
    "        mem=[-1]*(n*n)\n",
    "        def dfs(i:int,j:int)->int:\n",
    "            if i>=j-1:\n",
    "                return 0\n",
    "            if mem[i*n+j]!=-1:\n",
    "                return mem[i*n+j]\n",
    "            res=0\n",
    "            for mid in range(i+1,j):\n",
    "                left=dfs(i,mid)\n",
    "                right=dfs(mid,j)\n",
    "                # print(mid,val[i]*val[mid]*val[j])\n",
    "                res=max(res,left+right+val[i]*val[mid]*val[j])\n",
    "            mem[i*n+j]=res\n",
    "            # print(res)\n",
    "            return res\n",
    "        return dfs(0,n-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCoins1(self, nums: List[int]) -> int:\n",
    "        nums.insert(0,1)\n",
    "        nums.insert(len(nums),1)\n",
    "\n",
    "        store=[[0]*len(nums) for i in range(len(nums))]\n",
    "\n",
    "        def range_best(i,j):\n",
    "            m=0\n",
    "            for k in range(i+1,j):\n",
    "                left=store[i][k]\n",
    "                right=store[k][j]\n",
    "\n",
    "                a=left+right+nums[i]*nums[k]*nums[j]\n",
    "                if a>m:\n",
    "                    m=a\n",
    "            store[i][j]=m\n",
    "\n",
    "        for n in range(2,len(nums)):\n",
    "            for i in range(0,len(nums)-n):\n",
    "                range_best(i,i+n)\n",
    "        return store[0][len(nums)-1]\n",
    "    def maxCoins2(self, nums: List[int]) -> int:\n",
    "        nums.insert(0,1)\n",
    "        nums.insert(len(nums),1)\n",
    "        n=len(nums)\n",
    "        dp=[[0]*n for _ in range(n)]\n",
    "\n",
    "        for l in range(2,len(nums)):\n",
    "            #print(l)\n",
    "            for i in range(0,len(nums)-l):\n",
    "                j=i+l\n",
    "                #print(i,j)\n",
    "                for k in range(i+1,j):\n",
    "                    dp[i][j]=max(dp[i][k]+dp[k][j]+nums[i]*nums[k]*nums[j],dp[i][j])\n",
    "        print(dp)\n",
    "        return dp[0][-1]\n",
    "    def maxCoins4(self, nums: List[int]) -> int:\n",
    "        nums.insert(0,1)\n",
    "        nums.insert(len(nums),1)\n",
    "        n=len(nums)\n",
    "        dp=[[-1]*(n+1) for _ in range(n+1)]\n",
    "\n",
    "        def dfs(i,j):\n",
    "            if j-i<=1:\n",
    "                dp[i][j]=0\n",
    "                return 0\n",
    "            if dp[i][j]!=-1:\n",
    "                return dp[i][j]\n",
    "            for k in range(i+1,j):\n",
    "                tmp=dfs(i,k)+dfs(k,j)+nums[i]*nums[k]*nums[j]\n",
    "                dp[i][j]=max(dp[i][j],tmp)\n",
    "            return dp[i][j]\n",
    "        return dfs(0,len(nums)-1)\n",
    "\n",
    "    def maxCoins3(self, nums: List[int]) -> int:\n",
    "        nums.insert(0,1)\n",
    "        nums.insert(len(nums),1)\n",
    "        n=len(nums)\n",
    "\n",
    "        dp=[[0]*n for _ in range(n)]\n",
    "        #dp[i][j] i,j开区间的最大数量\n",
    "        \n",
    "        for l in range(2,n):\n",
    "            for i in range(n-l):\n",
    "                j=i+l\n",
    "                for k in range(i+1,j):\n",
    "                    dp[i][j]=max(dp[i][k]+dp[k][j]+nums[i]*nums[k]*nums[j],dp[i][j])\n",
    "        return dp[0][n-1]\n",
    "\n",
    "    def maxCoins(self, nums: List[int]) -> int:\n",
    "        nums.insert(0,1)\n",
    "        nums.insert(len(nums),1)\n",
    "        n=len(nums)\n",
    "        dp=[[-1]*(n+1) for _ in range(n+1)]\n",
    "\n",
    "        def dfs(i,j):\n",
    "            if i>=j-1:\n",
    "                dp[i][j]=0\n",
    "                return 0\n",
    "            if dp[i][j]!=-1:\n",
    "                return dp[i][j]\n",
    "            \n",
    "            for k in range(i+1,j):\n",
    "                tmp=dfs(i,k)+dfs(k,j)+nums[i]*nums[k]*nums[j]\n",
    "                dp[i][j]=max(dp[i][j],tmp)\n",
    "            \n",
    "            return dp[i][j]\n",
    "        print(dp)\n",
    "        return dfs(0,len(nums)-1)\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCoins(self, nums: List[int]) -> int:\n",
    "        nums = [1] + nums + [1]\n",
    "        nums = tuple(nums)\n",
    "        @lru_cache(None)\n",
    "        def dp(nums):\n",
    "            if len(nums) == 3:return nums[1] * nums[0] * nums[-1]\n",
    "            c = 0\n",
    "            for i in range(1, len(nums)-1):\n",
    "                # c = max(dp(nums[:i] + nums[i+1:]) + nums[i] * nums[i+1] * nums[i-1], c)\n",
    "                c = max(dp(nums[:i+1]) + dp(nums[i:]) + nums[i] * nums[0] * nums[-1], c)\n",
    "            return c\n",
    "        return dp(nums)\n",
    "\n",
    "\n",
    "        # memo = dict()\n",
    "        # nums = [1] + nums + [1]\n",
    "        # def dp(nums):\n",
    "        #     t = tuple(nums)\n",
    "        #     if t in memo:return memo[t]\n",
    "        #     if len(nums) == 3:return nums[1]\n",
    "        #     memo[t] = 0\n",
    "        #     for i in range(1, len(nums)-1):\n",
    "        #         memo[t] = max(dp(nums[:i] + nums[i+1:]) + nums[i] * nums[i+1] * nums[i-1], memo[t])\n",
    "        #     return memo[t]\n",
    "        # return dp(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCoins(self, nums: List[int]) -> int:\n",
    "        # \"\"\"\n",
    "        # 暴力解法\n",
    "        # \"\"\"\n",
    "        # n = len(nums)\n",
    "        # nums.insert(0, 1)\n",
    "        # nums.insert(len(nums), 1)\n",
    "        # print(n, len(nums))\n",
    "        # print(nums)\n",
    "        # self.ans = 0\n",
    "        # def dfs(i, sum, nums):\n",
    "        #     if i == n:\n",
    "        #         if sum >= self.ans:\n",
    "        #             self.ans = sum\n",
    "        #         return\n",
    "        #     for j in range(1, len(nums) - 1):\n",
    "        #         sum += nums[j - 1] * nums[j] * nums[j + 1]\n",
    "        #         dfs(i + 1, sum, nums[:j] + nums[j + 1:])\n",
    "        #         sum -= nums[j - 1] * nums[j] * nums[j + 1]\n",
    "\n",
    "        # dfs(0, 0, nums)\n",
    "        # return self.ans\n",
    "        nums.insert(0, 1)\n",
    "        nums.insert(len(nums), 1)\n",
    "        print(nums)\n",
    "        dp = [[0] * (len(nums)) for _ in range(len(nums))]\n",
    "        for i in range(len(nums) - 3, -1, -1):\n",
    "            for j in range(i + 2, len(nums)):\n",
    "                for k in range(i + 1, j):\n",
    "                    dp[i][j] = max(dp[i][j], \n",
    "                    dp[i][k] + nums[i] * nums[k] * nums[j] + dp[k][j])\n",
    "        print(dp)\n",
    "        return dp[0][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCoins(self, nums: List[int]) -> int:\n",
    "        new_nums = [1] + nums + [1]\n",
    "        memory = {}\n",
    "        return self.dfs(0, len(new_nums) - 1, new_nums, memory)\n",
    "\n",
    "    def dfs(self, i: int, j: int, nums: List[int], memory) -> int:\n",
    "        if (i, j) in memory:\n",
    "            return memory[(i, j)]\n",
    "        if j - i == 1:\n",
    "            return 0\n",
    "        if j - i == 2:\n",
    "            return nums[i] * nums[i + 1] * nums[j]\n",
    "        max_value = 0\n",
    "        for k in range(i + 1, j):\n",
    "            value_now = self.dfs(i, k, nums, memory) + self.dfs(k, j, nums, memory) + nums[i] * nums[k] * nums[j]\n",
    "            max_value = max(max_value, value_now)\n",
    "        memory[(i, j)] = max_value\n",
    "        return max_value"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCoins(self, nums: List[int]) -> int:\n",
    "        n = len(nums)+2\n",
    "        a = [1]+nums+[1]\n",
    "        \n",
    "        dp = {} #(i,j):v, v is the maximum gain in (i,j)\n",
    "        for i in range(0,n-1):\n",
    "            dp[(i,i+1)] = 0\n",
    "            \n",
    "        for d in range(2, n):\n",
    "            for i in range(0, n-d):\n",
    "                ma = 0\n",
    "                for k in range(i+1, i+d):\n",
    "                    tmp = dp[(i, k)] + dp[(k,i+d)] + a[i]*a[k]*a[i+d]\n",
    "                    if tmp>ma:\n",
    "                        ma = tmp\n",
    "                dp[(i,i+d)] = ma\n",
    "\n",
    "\n",
    "        return dp[(0, n-1)]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCoins(self, nums: List[int]) -> int:\n",
    "        nums = [1]+nums+[1]\n",
    "        @cache\n",
    "        def back(l,r):\n",
    "            if r-l <= 1:return 0\n",
    "            return max(nums[l]*nums[r]*nums[i]+back(l,i)+back(i,r) for i in range(l+1,r))\n",
    "        res = back(0,len(nums)-1)\n",
    "        del back\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCoins(self, nums: List[int]) -> int:\n",
    "        nums = [1]+nums+[1]\n",
    "        dp = [[0]*len(nums) for _ in range(len(nums)+1)]\n",
    "        @lru_cache(None)\n",
    "        def findbest(left,right):\n",
    "            m = 0\n",
    "            for i in range(left+1,right):\n",
    "                l = dp[left][i]\n",
    "                r = dp[i][right]\n",
    "                m = max(m,l+r+nums[i]*nums[left]*nums[right])       \n",
    "            dp[left][right]=m\n",
    "        for l in range(2,len(nums)):\n",
    "            for i in range(len(nums)-l):\n",
    "                findbest(i,i+l)\n",
    "        return dp[0][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCoins(self, nums) -> int:\n",
    "        dp = {}\n",
    "        nums = [1] + nums + [1]\n",
    "        for i in range(len(nums) - 2, -1, -1):\n",
    "            for j in range(i + 1, len(nums)):\n",
    "                if i < j - 1:\n",
    "                    dp[(i, j)] = max([nums[i] * nums[k] * nums[j] + dp[(i, k)] + dp[(k, j)] for k in range(i + 1, j)])\n",
    "                else:\n",
    "                    dp[(i, j)] = 0\n",
    "        return dp[(0, len(nums) - 1)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCoins(self, nums: List[int]) -> int:\n",
    "        self.nums = [1] + nums + [1]\n",
    "        self.cache = dict()\n",
    "        for i in range(1, len(self.nums)-1):\n",
    "            self.solve(0, i)\n",
    "\n",
    "        return self.solve(0, len(self.nums) - 1)\n",
    "\n",
    "    def solve(self, start, end):\n",
    "        if (start, end) in self.cache:\n",
    "            return self.cache[(start, end)]\n",
    "\n",
    "        if end == start + 1:\n",
    "            return 0\n",
    "\n",
    "        res = 0\n",
    "        for i in range(start+1, end):\n",
    "            res = max(res, self.solve(start, i) + self.solve(i, end) + self.nums[i] * self.nums[start] * self.nums[end])\n",
    "\n",
    "        self.cache[(start, end)] = res\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCoins(self, nums: List[int]) -> int:\n",
    "\n",
    "        n = len(nums)\n",
    "\n",
    "        val = [1] + nums + [1]\n",
    "        dp = [[-float(\"inf\") for i in range(n+2)]for j in range(n+2)]\n",
    "        def solve(left,right):\n",
    "            if left >= right-1:\n",
    "                return 0\n",
    "\n",
    "            if dp[left][right] != -float(\"inf\"):\n",
    "                return dp[left][right]\n",
    "\n",
    "            best = 0\n",
    "            for i in range(left+1,right):\n",
    "                total = val[left] * val[i] * val[right]\n",
    "                total += solve(left,i) + solve(i,right)\n",
    "                best = max(best,total)\n",
    "            dp[left][right] = best\n",
    "            return best\n",
    "        \n",
    "        return solve(0,n+1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def maxCoins(self, nums: List[int]) -> int:\n",
    "        dp = [[0 for _ in range(len(nums) + 2)] for _ in range(len(nums) + 2)]\n",
    "        nums = [1] + nums + [1]\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def cal(i, j):\n",
    "            m = 0\n",
    "            for k in range(i + 1, j):\n",
    "                left = dp[i][k]\n",
    "                right = dp[k][j]\n",
    "                m = max(m, left + nums[i] * nums[k] * nums[j] + right)\n",
    "            dp[i][j] = m\n",
    "\n",
    "        for i in range(2, len(nums)):\n",
    "            # 注意循环条件\n",
    "            for j in range(len(nums) - i):\n",
    "                cal(j, i + j)\n",
    "        return dp[0][len(nums) - 1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCoins(self, nums: List[int]) -> int:\n",
    "        memo = {}\n",
    "\n",
    "        nums = [1] + nums + [1]\n",
    "\n",
    "\n",
    "        def f(nums):\n",
    "            assert len(nums) >=2, nums\n",
    "            if len(nums) == 2:\n",
    "                return 0\n",
    "            elif len(nums) == 3:\n",
    "                return nums[0]*nums[1]*nums[2]\n",
    "            else:\n",
    "                t = tuple(nums)\n",
    "                if t in memo:\n",
    "                    return memo[t]\n",
    "                ans = -1\n",
    "                for i in range(1,len(nums)-1):\n",
    "                    ans = max(ans,f(nums[0:i+1])+f(nums[i:])+nums[0]*nums[i]*nums[-1])\n",
    "                memo[t] = ans\n",
    "                return ans\n",
    "\n",
    "        return f(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def maxCoins(self, nums: List[int]) -> int:\n",
    "        #矩阵链乘法\n",
    "        #假设最后一个戳的气球是k\n",
    "        #S(-1,n)=S(-1,k)+S(k,n)+(V-1*Vk*Vn)\n",
    "        s=np.zeros([len(nums)+2,len(nums)+2])\n",
    "        Q=[1]+nums+[1]\n",
    "        print(Q)\n",
    "        for i in range(len(Q)-1,-1,-1):\n",
    "            for j in range(len(Q)):\n",
    "                for k in range(i+1,j):\n",
    "                    s[i,j]=max(s[i,j],s[i,k]+s[k,j]+Q[i]*Q[k]*Q[j])\n",
    "        return int(s[0][len(Q)-1])        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        #暴力超时\n",
    "        # if len(nums)==0:\n",
    "        #     return 0\n",
    "        # if len(nums)==1:\n",
    "        #     return nums[0]\n",
    "        # if len(nums)==2:\n",
    "        #     return nums[0]*nums[1]+max(nums)\n",
    "\n",
    "        # def f(x,y,z):\n",
    "        #     return max(x*y+y*z+max(y,z),x*y+y*z+max(x,y),x*y*z+x*z+max(x,z))\n",
    "        \n",
    "        # def coin(nums,i):\n",
    "        #     if i==0:\n",
    "        #         left=0\n",
    "        #         llist=[]\n",
    "        #     else:\n",
    "        #         left=nums[i-1]\n",
    "        #         llist=nums[:i]\n",
    "\n",
    "        #     if i==len(nums)-1:\n",
    "        #         right=1\n",
    "        #         rlist=[]\n",
    "        #     else:\n",
    "        #         right=nums[i+1]\n",
    "        #         rlist=nums[i+1:]\n",
    "            \n",
    "        #     if len(nums)==3:\n",
    "        #         return f(nums[0],nums[1],nums[2])\n",
    "            \n",
    "        #     new_nums=llist+rlist\n",
    "        #     print(nums,nums[i],new_nums)\n",
    "        #     m=0\n",
    "        #     for j in range(len(new_nums)):\n",
    "        #         m=max(m,left*nums[i]*right+coin(new_nums,j))\n",
    "        #     return m\n",
    "\n",
    "        # coin_max=0\n",
    "        # for k in range(len(nums)):\n",
    "        #     coin_max=max(coin_max,coin(nums,k))\n",
    "\n",
    "        # return coin_max"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "\n",
    "class Solution:\n",
    "    def maxCoins(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        nums2 = [1] + nums + [1]\n",
    "        dp = np.zeros((n+2, n+2), dtype=int)\n",
    "        for j in range(n):\n",
    "            for i in range(1, n+1-j):\n",
    "                    dp[i-1][i+j+1] = max(dp[i-1][i+k]+dp[i+k][i+j+1]+nums2[i-1]*nums2[i+k]*nums2[i+j+1] for k in range(j+1))\n",
    "        return dp[0, n+1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCoins(self, nums: List[int]) -> int:\n",
    "        @lru_cache(None)\n",
    "        def help(A):\n",
    "            if len(A) <= 2:\n",
    "                return 0\n",
    "            res = 0\n",
    "            for k in range(1, len(A)-1):\n",
    "                if 2<k<len(A)-2 and A[k+1]==A[k]==A[k-1]==A[k-2]:\n",
    "                    continue\n",
    "                res = max(res, help(A[:k+1]) + help(A[k:]) + A[k]*A[0]*A[-1])\n",
    "            return res\n",
    "\n",
    "        return help(tuple([1]+nums+[1]))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCoins(self, nums: List[int]) -> int:\n",
    "        @lru_cache(None)\n",
    "        def help(A):\n",
    "            if len(A) <= 2:\n",
    "                return 0\n",
    "            return max(help(A[:k + 1]) + help(A[k:]) + A[k] * A[0] * A[-1] for k in range(1, len(A) - 1))\n",
    "\n",
    "        return help(tuple([1] + nums + [1]))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def maxCoins(self, nums: List[int]) -> int:\n",
    "        nums = [1]+nums+[1]\n",
    "        l = len(nums)\n",
    "        dp = np.zeros((l, l))\n",
    "        for i in range(l-1, -1, -1):\n",
    "            for j in range(l):\n",
    "                if i >= j:\n",
    "                    pass\n",
    "                else:\n",
    "                    for k in range(i+1, j):\n",
    "                        dp[i, j] = max(dp[i, j], dp[i, k] + dp[k, j] + nums[i]*nums[k]*nums[j])\n",
    "        return int(dp[0, l-1])\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "\n",
    "class Solution:\n",
    "    def maxCoins(self, nums: List[int]) -> int:\n",
    "        N = len(nums)\n",
    "        nums = [1] + nums + [1]\n",
    "        dp = np.zeros((N + 2, N + 2)).astype('int')\n",
    "        for l in range(1, N + 1):  # 枚举区间长度[1, N]\n",
    "            for left in range(1, N + 2 - l):  # 枚举开区间启始位置[0, N - 1]\n",
    "                right = left + l - 1\n",
    "                for mid in range(left, right + 1):\n",
    "                    val = nums[left - 1] * nums[mid] * nums[right + 1]\n",
    "                    if left <= mid - 1:\n",
    "                        val += dp[left][mid - 1]\n",
    "                    if mid + 1 <= right:\n",
    "                        val += dp[mid + 1][right]\n",
    "                    dp[left][right] = max(dp[left][right], val)\n",
    "        return dp[1, N]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCoins(self, nums: List[int]) -> int:\n",
    "        val = [1] + nums + [1]\n",
    "        n = len(nums)\n",
    "        @lru_cache(None)\n",
    "        def solve(left, right):\n",
    "            if left >= right:\n",
    "                return 0\n",
    "            \n",
    "            ans = 0\n",
    "            for i in range(left+1, right):\n",
    "                total = val[left]*val[i]*val[right] + solve(left,i) + solve(i, right)\n",
    "                ans = max(ans, total)\n",
    "            \n",
    "            return ans\n",
    "        \n",
    "        return solve(0, n+1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def maxCoins(self, nums: List[int]) -> int:\n",
    "        memo = {}\n",
    "        return self.helper(memo, nums, 1, 1, 0, len(nums)-1)\n",
    "\n",
    "    def helper(self, memo, nums, left, right, start, end):\n",
    "        # print(memo, start, end, left, right)\n",
    "        if start > end:\n",
    "            memo[(start, end)] = 0\n",
    "            # return 0\n",
    "        elif start == end:\n",
    "            memo[(start, end)] = nums[start]*left*right\n",
    "            # return nums[start]*left*right\n",
    "        else:\n",
    "            if (start, end) not in memo.keys(): \n",
    "                tmp = []\n",
    "                for i in range(start, end+1):\n",
    "                    tmp.append(nums[i]*left*right + self.helper(memo, nums, left, nums[i], start, i-1) + self.helper(memo, nums, nums[i], right, i+1, end))\n",
    "                # print(tmp)\n",
    "                memo[(start, end)] = max(tmp)\n",
    "                # return memo[(start, end)]\n",
    "        # print(memo, start, end, left, right)\n",
    "        return memo[(start, end)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCoins(self, a: List[int]) -> int:\n",
    "        a = [1] + a + [1]\n",
    "        @cache\n",
    "        def f(i, j): return 0 if j<=i else max(f(i, m) + f(m+1, j) + a[i-1]* a[m]*a[j] for m in range(i,j))\n",
    "        return f(1, len(a)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCoins(self, nums: List[int]) -> int:\n",
    "        new_nums = [1]+nums+[1]\n",
    "        n = len(new_nums)\n",
    "        dp = [[0 for _ in range(n)] for _ in range(n)]\n",
    "        seen = set()\n",
    "        def search(left,right):\n",
    "            if (left,right) in seen:\n",
    "                return dp[left][right]\n",
    "            tmp = 0\n",
    "            for k in range(left+1,right):\n",
    "                left_to_k = search(left,k)\n",
    "                k_to_right = search(k,right)\n",
    "                current = left_to_k + k_to_right + new_nums[left]*new_nums[right]*new_nums[k]\n",
    "                tmp = max(tmp,current)\n",
    "            dp[left][right] = tmp\n",
    "            seen.add((left,right))\n",
    "            return dp[left][right]\n",
    "        return search(0,n-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCoins(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        val = [1] + nums + [1]\n",
    "        \n",
    "        @lru_cache(None)\n",
    "        def solve(left: int, right: int) -> int:\n",
    "            if left >= right - 1:\n",
    "                return 0\n",
    "            \n",
    "            best = 0\n",
    "            for i in range(left + 1, right):\n",
    "                total = val[left] * val[i] * val[right]\n",
    "                total += solve(left, i) + solve(i, right)\n",
    "                best = max(best, total)\n",
    "            \n",
    "            return best\n",
    "\n",
    "        return solve(0, n + 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCoins(self, nums: List[int]) -> int:\n",
    "\n",
    "        n = len(nums)\n",
    "        vals = [1] + nums + [1]\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(i, j):\n",
    "            res = 0\n",
    "            for k in range(i+1, j):\n",
    "                tmp = vals[i+1] * vals[k+1] * vals[j+1] + dfs(i, k) + dfs(k, j)\n",
    "                if tmp > res:\n",
    "                    res = tmp\n",
    "            return res\n",
    "\n",
    "        return dfs(-1, n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCoins(self, nums: List[int]) -> int:\n",
    "        m = len(nums)\n",
    "        nums.insert(0, 1)\n",
    "        nums.append(1)\n",
    "        @lru_cache(None)\n",
    "        def solve(i, j):\n",
    "            if i>=j-1:\n",
    "                return 0\n",
    "            max_value = 0\n",
    "            for mid in range(i+1, j):\n",
    "                max_value = max(max_value, nums[i] * nums[j] * nums[mid] + solve(i, mid) + solve(mid, j))\n",
    "            return max_value\n",
    "        \n",
    "        return solve(0, m+1)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCoins(self, nums: List[int]) -> int:\n",
    "        @lru_cache(None)\n",
    "        def dfs(l: int, r: int) -> int:\n",
    "            # if l + 1 >= r:\n",
    "            #     return 0\n",
    "            maxCoins = 0\n",
    "            for i in range(l + 1, r):\n",
    "                curCoins = nums[l] * nums[i] * nums[r]\n",
    "                curCoins += dfs(l, i)\n",
    "                curCoins += dfs(i, r)\n",
    "                maxCoins = max(maxCoins, curCoins)\n",
    "            # print(nums[l:r], maxCoins)\n",
    "            return maxCoins\n",
    "        \n",
    "        # nums.insert(0, 1)\n",
    "        # nums.append(1)\n",
    "        nums = [1] + nums + [1]\n",
    "        return dfs(0, len(nums) - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCoins(self, nums: List[int]) -> int:\n",
    "        new_nums = [1] + [_ for _ in nums if _ != 0] + [1]\n",
    "        n = len(new_nums)\n",
    "        cache = {}\n",
    "        def solve(left, right):\n",
    "            if (left, right) in cache:\n",
    "                return cache[(left, right)]\n",
    "            if left >= right - 1:\n",
    "                return 0\n",
    "            max_profit = 0\n",
    "            for i in range(left + 1, right):\n",
    "                max_profit = max(max_profit, solve(left, i) + solve(i, right) + new_nums[left] * new_nums[i] * new_nums[right])\n",
    "            cache[(left, right)] = max_profit\n",
    "            return max_profit\n",
    "        return solve(0, n - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCoins(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        arr = [1] + nums + [1]\n",
    "        d = {}\n",
    "        def dfs(left, right):\n",
    "            if (left, right) in d:\n",
    "                return d[left, right]\n",
    "            if left >= right:\n",
    "                return 0\n",
    "            res = 0\n",
    "            for i in range(left + 1, right):\n",
    "                total = arr[left] * arr[i] * arr[right]\n",
    "                total += dfs(left, i) + dfs(i, right)\n",
    "                res = max(res, total)\n",
    "            d[left, right] = res\n",
    "            return res\n",
    "        return dfs(0, n + 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCoins(self, nums: List[int]) -> int:\n",
    "        dic = {}\n",
    "        n = len(nums)\n",
    "        nums = [1] + nums + [1]\n",
    "        \n",
    "        def search(left, right):\n",
    "            if left > right:\n",
    "                return 0\n",
    "\n",
    "            if ((left, right)) in dic:\n",
    "                return dic[(left, right)]\n",
    "            \n",
    "            ans = 0\n",
    "            for i in range(left + 1, right):\n",
    "                tmp = nums[left] * nums[i] * nums[right]\n",
    "                tmp += search(left, i) + search(i, right)\n",
    "                ans = max(ans, tmp)\n",
    "            dic[(left, right)] = ans\n",
    "            return ans\n",
    "        \n",
    "        return search(0, n + 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCoins(self, nums: List[int]) -> int:\n",
    "        dp = dict()\n",
    "        nums.append(1)\n",
    "        nums = [1] + nums\n",
    "        n = len(nums)-1\n",
    "        def dfs(start,end):\n",
    "            if end - start <= 1: return 0\n",
    "            if end - start == 2: return nums[start]*nums[start+1]*nums[end]\n",
    "            if (start,end) in dp: return dp[(start,end)]\n",
    "            temp = nums[start] * nums[end]\n",
    "            out = max((nums[i]*temp + dfs(start,i) + dfs(i,end) for i in range(start+1,end)))\n",
    "            dp[(start,end)] = out\n",
    "            return out\n",
    "        return dfs(0,n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCoins(self, nums: List[int]) -> int:\n",
    "        nums.append(1)\n",
    "\n",
    "        mem = {}\n",
    "\n",
    "        def helper(i, j):\n",
    "            if i > j:\n",
    "                return 0\n",
    "            if i == j:\n",
    "                return nums[i-1] * nums[i] * nums[i+1]\n",
    "\n",
    "            if (i, j) in mem:\n",
    "                return mem[i, j]\n",
    "\n",
    "            mmax = -99999\n",
    "            for k in range(i, j+1):\n",
    "                temp = nums[i-1] * nums[j+1] * nums[k] + helper(i, k-1) + helper(k+1, j)\n",
    "                mmax = max(mmax, temp)\n",
    "            \n",
    "            mem[i, j] = mmax\n",
    "            return mmax\n",
    "        \n",
    "        return helper(0, len(nums)-2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np \n",
    "class Solution: # (8344ms)\n",
    "    def maxCoins(self, nums: List[int]) -> int:\n",
    "        nums = [1] + nums + [1]\n",
    "        n = len(nums)\n",
    "        dp = np.zeros([n, n])\n",
    "        for i in range(n):\n",
    "            dp[(i, i)] = 0\n",
    "            if i < n-1:\n",
    "                dp[(i, i+1)] = 0                                           \n",
    "        \n",
    "        for d in range(1, n+1):     \n",
    "            for left in range(n): \n",
    "                right = left+d-1\n",
    "                if right >=n: continue\n",
    "                score = 0\n",
    "                for k in range(left+1, right-1+1): \n",
    "                    score = max(score, nums[left] * nums[k] * nums[right] + dp[(left, k)] + dp[(k, right)])\n",
    "                dp[(left, right)] = score\n",
    "                \n",
    "        return int(dp[(0, n-1)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def maxCoins(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if n == 1:\n",
    "            return nums[0]\n",
    "        dp = [[0 for i in range(n+2)] for j in range(n+2)]\n",
    "        nums.insert(0, 1)\n",
    "        nums.append(1)\n",
    "        for k in range(2, n+2):\n",
    "            for i in range(n+2-k):\n",
    "                j = i + k\n",
    "                for x in range(i+1, j):\n",
    "                    dp[i][j] = max(dp[i][j], dp[i][x] + nums[i]*nums[x]*nums[j] + dp[x][j])\n",
    "\n",
    "        # print(np.array(dp))\n",
    "        return dp[0][n+1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    #分治法\n",
    "    def maxCoins(self, nums: List[int]) -> int:\n",
    "        nums = [1] + nums +[1]\n",
    "        n = len(nums)\n",
    "        rec = [[0] * n for _ in range(n)] #避免重复计算\n",
    "        \n",
    "        @lru_cache(None) #加上之后不再超出时间限制\n",
    "        def solve(left, right):\n",
    "            # 计算区间[left, right]内戳气球的最大得分，不含首尾，即solve(i, i+1)=0\n",
    "            if left >= right-1:\n",
    "                return 0\n",
    "            for i in range(left+1, right):\n",
    "                curr = nums[left] * nums[i] * nums[right] + solve(left, i) + solve(i, right)\n",
    "                rec[left][right] = max(rec[left][right], curr)\n",
    "            return rec[left][right]\n",
    "        \n",
    "        return solve(0, n-1)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCoins(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        val = [1] + nums + [1]\n",
    "        \n",
    "        dp=[[-1]*(n+2)for i in range(n+2)]\n",
    "        @lru_cache(None)\n",
    "        def solve(left: int, right: int) -> int:\n",
    "            if left >= right - 1:\n",
    "                return 0\n",
    "            best = 0\n",
    "            for i in range(left + 1, right):\n",
    "               # total = val[left] * val[i] * val[right] +solve(left, i) + solve(i, right)\n",
    "                best = max(best, val[left] * val[i] * val[right] +solve(left, i) + solve(i, right))\n",
    "            dp[left][right]=best\n",
    "            return best\n",
    "\n",
    "        return solve(0, n + 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np  \n",
    "class Solution:\n",
    "    def maxCoins(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        nums = [1] + nums + [1]\n",
    "        # OPT = np.zeros((n+2, n+2)) # init the   2-D array as zeros\n",
    "        OPT = [[0] * (n+2) for _ in range(n+2)]\n",
    "        for g in range(2, n+2): # Traverse the gap between i and j(i.e., j - i)\n",
    "            for i in range(0, n - g + 2):\n",
    "                j = i + g\n",
    "                # j = min(i + g, n + 1) # j can't be larger than n\n",
    "                if i == j + 2: #\n",
    "                    OPT[i][j] = nums[i] * nums[i+1] * nums[i+2]\n",
    "                else: # we have to consider the invalid index\n",
    "                    for k in range(i+1, j):\n",
    "                        OPT[i][j] = max(OPT[i][j], nums[i] * nums[k] * nums[j] + OPT[i][k] + OPT[k][j])\n",
    "        # print(OPT)\n",
    "        return int(OPT[0][n+1])\n",
    "    # ret = findmax2(nums, 4)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def maxCoins(self, nums: List[int]) -> int:\n",
    "        nums_n = [1] + nums + [1]\n",
    "        n = len(nums_n)\n",
    "        dp = [[0 for _ in range(n)] for _ in range(n)]\n",
    "        for diff in range(2, n):\n",
    "            for i in range(0, n-diff):\n",
    "                for j in range(1, diff):\n",
    "                    dp[i][i+diff] = max(dp[i][i+diff], dp[i][i+j]+dp[i+j][i+diff]+nums_n[i]*nums_n[i+j]*nums_n[i+diff])\n",
    "        return int(dp[0][n-1])\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCoins(self, nums: List[int]) -> int:\n",
    "        # def(i, j) = max {def(i, k) + def(k , j)+nums[i][j][k]} | i<k<j \n",
    "        #当i、j相邻时为最小子问题\n",
    "\n",
    "        #创建虚拟边界\n",
    "        nums = [1] + nums + [1]\n",
    "        memo = {}\n",
    "        def fenzhi(i, j):\n",
    "        #边界\n",
    "            if j-i == 1:\n",
    "                return 0\n",
    "            try:\n",
    "                return memo[(i, j)]\n",
    "            except:\n",
    "                max_ = float('-inf')\n",
    "                #k为引爆位置\n",
    "                for k in range(i+1, j):\n",
    "                    new_ = fenzhi(i, k) + nums[i]*nums[j]*nums[k] + fenzhi(k, j)\n",
    "                    max_ = max_ if max_ > new_ else  new_\n",
    "                memo[(i, j)] = max_\n",
    "                return max_\n",
    "        return fenzhi(0, len(nums)-1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def maxCoins(self, ballons: List[int]) -> int:\n",
    "\n",
    "        n = len(ballons)\n",
    "        nums = [1 for i in range(n+2)]\n",
    "        nums[1:n+1] = [_ for _ in ballons]\n",
    "        visited = [[-1 for i in range(n+2)] for _ in range(n+2)]\n",
    "        dp = [[0 for i in range(n+2)] for _ in range(n+2)]\n",
    "        res = self.search_hit_route(nums, dp, visited, 1, n)\n",
    "        return int(res)\n",
    "    \n",
    "    # @lru_cache(None)\n",
    "    def search_hit_route(self, nums, dp, visited, left, right):\n",
    "\n",
    "        if visited[left][right] > 0:\n",
    "            return dp[left][right]\n",
    "        res = 0\n",
    "        for k in range(left, right+1):\n",
    "            midValue = nums[left-1] * nums[k] * nums[right+1]\n",
    "            leftValue = self.search_hit_route(nums, dp, visited, left, k - 1)\n",
    "            rightValue = self.search_hit_route(nums, dp, visited, k+1, right)\n",
    "            total = leftValue+midValue+rightValue\n",
    "            res = max(total, res)\n",
    "\n",
    "        visited[left][right] = 1\n",
    "        dp[left][right] = res\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCoins(self, nums: List[int]) -> int:\n",
    "        nums = [1] + nums + [1]\n",
    "        @lru_cache(None)\n",
    "        def dfs(i, j):\n",
    "            Mul = nums[i] * nums[j]\n",
    "            return max(\n",
    "                [\n",
    "                    dfs(i, k) + dfs(k, j) + nums[k] * Mul \\\n",
    "                    for k in range(i + 1, j)\n",
    "                ]\n",
    "            ) if i + 1 < j else 0\n",
    "\n",
    "        return dfs(0, len(nums) - 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCoins(self, nums: List[int]) -> int:\n",
    "        balls = [1] + nums + [1]\n",
    "        memo = {}\n",
    "        def fillBall(left, right):\n",
    "            id = left * 1000 + right\n",
    "            if id not in memo:\n",
    "                if left >= right-1:\n",
    "                    return 0\n",
    "                max_val = 0\n",
    "                for i in range(left+1, right):\n",
    "                    cur = balls[i] * balls[left] * balls[right]\n",
    "                    cur += fillBall(left, i) + fillBall(i ,right)\n",
    "                    max_val = max(max_val, cur)\n",
    "                memo[id] = max_val\n",
    "            return memo[id]\n",
    "        return fillBall(0, len(balls)-1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCoins(self, nums: List[int]) -> int:\n",
    "        \n",
    "        meno = dict()\n",
    "        # 添加开头的0\n",
    "        point = [1] + nums + [1]\n",
    "        dp = [[0] * (len(nums) + 2) for _ in range(len(nums) + 2)]\n",
    "        for i in range(len(nums) - 1, -1, -1):\n",
    "            for j in range(i + 2, len(nums) + 2):\n",
    "                if (i, j) in meno:\n",
    "                    dp[i][j] = meno[(i, j)]\n",
    "                else:\n",
    "                    for k in range(i + 1, j):\n",
    "                        dp[i][j] = max(dp[i][j], \n",
    "                            dp[i][k] + dp[k][j] + point[i] * point[j] * point[k])\n",
    "                    meno[(i, j)] = dp[i][j]\n",
    "        return dp[0][int(len(nums) + 1)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "class Solution:\n",
    "    def maxCoins(self, nums: List[int]) -> int:\n",
    "        self.nums=[1]+nums+[1]\n",
    "        return self.deep(0,len(self.nums)-1)\n",
    "    @lru_cache(None)\n",
    "    def deep(self,i,j):\n",
    "        if i>=j-1:\n",
    "            return 0\n",
    "        coinmax=0\n",
    "        for k in range(i+1,j):\n",
    "            if self.nums[k]==0:\n",
    "                continue\n",
    "            coin=self.deep(i,k)+self.deep(k,j)+self.nums[k]*self.nums[i]*self.nums[j]\n",
    "            coinmax=max(coinmax,coin)\n",
    "        return coinmax"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCoins(self, nums: List[int]) -> int:\n",
    "        @lru_cache(100000)\n",
    "        def dfs(l, r):\n",
    "            if l >= r - 1:\n",
    "                return 0\n",
    "            best = 0\n",
    "            for i in range(l + 1, r):\n",
    "                best = max(best, nums[l] * nums[r] * nums[i] + dfs(l, i) + dfs(i, r))\n",
    "            return best\n",
    "\n",
    "        nums = [1] + nums + [1]\n",
    "        return  dfs(0, len(nums) - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCoins(self, nums: List[int]) -> int:\n",
    "        @lru_cache(maxsize=100000)\n",
    "        def dp(start_, end_):\n",
    "            nonlocal nums\n",
    "            #返回(start_, end_)之间选取的元素\n",
    "            #if end_-start_<2: return 0\n",
    "            tem = 0\n",
    "            # print(nums)\n",
    "            # print(start_, end_)\n",
    "            for idx in range(start_+1, end_):\n",
    "                #_ = dp(start_, idx)+dp(idx, end_)\n",
    "                tem = max(tem, dp(start_, idx)+dp(idx, end_)+nums[idx]*nums[start_]*nums[end_])\n",
    "            return tem\n",
    "        \n",
    "        n = len(nums)\n",
    "        nums = [1]+nums+[1]\n",
    "        return dp(0, n+1)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCoins(self, nums: List[int]) -> int:\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def getMax(left, right, i, j) -> int:\n",
    "            if i > j:\n",
    "                return 0\n",
    "            # if (left, right, i, j) in memo:\n",
    "            #     return memo[(left, right, i, j)]\n",
    "            ans = 0\n",
    "            for idx in range(i, j+1):\n",
    "                cur = left * nums[idx] * right\n",
    "                cur += getMax(left, nums[idx], i, idx-1)\n",
    "                cur += getMax(nums[idx], right, idx+1, j)\n",
    "                ans = max(ans, cur)\n",
    "            # memo[(left, right, i, j)] = ans\n",
    "            return ans\n",
    "        \n",
    "        return getMax(1, 1, 0, len(nums)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.nums = []\n",
    "\n",
    "    def maxCoins(self, nums: List[int]) -> int:\n",
    "        self.nums = [1] + nums + [1]\n",
    "        size = len(nums)\n",
    "        return self.find_max(1, size + 1)\n",
    "\n",
    "    @lru_cache(None)\n",
    "    def find_max(self, m: int, n: int) -> int:\n",
    "        if (m == n):\n",
    "            return 0\n",
    "        else:\n",
    "            result = 0\n",
    "            for i in range(m , n):\n",
    "                result = max(result, self.find_max(m,i) + \n",
    "                             self.nums[m - 1] * self.nums[i] * self.nums[n] +\n",
    "                             self.find_max(i + 1, n))\n",
    "            return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCoins(self, nums: List[int]) -> int:\n",
    "        self.nums=[1]+nums+[1]\n",
    "        n=len(nums)\n",
    "        return self.func(0,n+1)\n",
    "    @lru_cache(None)\n",
    "    def func(self,left,right):\n",
    "        if left>=right-1:\n",
    "            return 0 \n",
    "        res=0\n",
    "        for i in range(left+1,right):\n",
    "            total=self.nums[left]*self.nums[i]*self.nums[right]\n",
    "            total+=self.func(left,i)+self.func(i,right)\n",
    "            res=max(res,total)\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCoins(self, nums: List[int]) -> int:\n",
    "        N = len(nums)\n",
    "        @cache\n",
    "        def dfs(start, end):\n",
    "            if start + 2 > end:\n",
    "                return 0 \n",
    "            ns = nums[start] if start >= 0 else 1\n",
    "            ne = nums[end] if end < N else 1\n",
    "            res = 0\n",
    "            base = ns * ne\n",
    "            for mid in range(start + 1, end):\n",
    "                add = base * nums[mid]\n",
    "                cur = dfs(start, mid) + dfs(mid, end) + add\n",
    "                res = max(res, cur)\n",
    "            return res\n",
    "        return dfs(-1, N)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import cache\r\n",
    "class Solution:\r\n",
    "    def maxCoins(self, nums: List[int]) -> int:\r\n",
    "        return self.method2(nums)\r\n",
    "\r\n",
    "    def method1(self, nums):\r\n",
    "        if nums is None or len(nums) == 0:\r\n",
    "            return 0\r\n",
    "        # 从左到右遍历尝试 哪个第一个被打破 返回最大得分\r\n",
    "        def dfs(nums):\r\n",
    "            if len(nums) == 1:\r\n",
    "                return nums[0]\r\n",
    "            max_val = 0\r\n",
    "            for i in range(len(nums)):\r\n",
    "                left_val = nums[i-1] if i-1>=0 else 1\r\n",
    "                right_val = nums[i+1] if i+1<len(nums) else 1\r\n",
    "                pro = nums[i]*left_val*right_val + dfs(nums[0:i]+nums[i+1:])\r\n",
    "                max_val = max(max_val, pro)\r\n",
    "            return max_val\r\n",
    "        return dfs(nums)\r\n",
    "    \r\n",
    "    def method2(self, nums):\r\n",
    "        # 预处理nums\r\n",
    "        pre_nums = [1] * (len(nums)+2)\r\n",
    "        pre_nums[1:len(nums)+1] = nums\r\n",
    "        # 范围尝试模型， 最后一个打破气球得分最大的返回值\r\n",
    "        # 先打爆i 到 j 上所有的气球\r\n",
    "        @cache\r\n",
    "        def dfs(i, j):\r\n",
    "            if i == j:\r\n",
    "                return pre_nums[i-1] * pre_nums[i] * pre_nums[i+1]\r\n",
    "            \r\n",
    "            max_val = max(pre_nums[i-1] * pre_nums[j] * pre_nums[j+1] + dfs(i,j-1)\r\n",
    "                , pre_nums[i-1] * pre_nums[i] * pre_nums[j+1] + dfs(i+1, j))\r\n",
    "            for k in range(i+1, j):\r\n",
    "                pro = pre_nums[i-1]*pre_nums[j+1]*pre_nums[k] + dfs(i,k-1) + dfs(k+1,j)\r\n",
    "                max_val = max(max_val, pro)\r\n",
    "            return max_val\r\n",
    "        return dfs(1, len(nums))\r\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCoins(self, nums: List[int]) -> int:\n",
    "        nums=[1]+nums+[1]\n",
    "        dp={}\n",
    "        def dfs(l,r):\n",
    "            if l>r:\n",
    "                return 0\n",
    "            if (l,r) in dp:\n",
    "                return dp[(l,r)]\n",
    "            dp[(l,r)]=0\n",
    "            for i in range(l,r+1):\n",
    "                coins=nums[l-1]*nums[i]*nums[r+1]\n",
    "                coins+=dfs(l,i-1)+dfs(i+1,r)\n",
    "                dp[(l,r)]=max(dp[(l,r)],coins)\n",
    "            return dp[(l,r)]\n",
    "        return dfs(1,len(nums)-2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCoins(self, nums: List[int]) -> int:\n",
    "        nums=[1]+nums+[1]  #添加两个虚拟气球\n",
    "        dp={}  #临时空数组\n",
    "        def dfs(l,r):  #定义深度优先搜索函数\n",
    "            if l>r:  #超过边界\n",
    "                return 0 #返回0\n",
    "            if (l,r)in dp: #未超过边界\n",
    "                return dp[(l,r)]  #返回dp\n",
    "            dp[(l,r)]=0\n",
    "            for i in range(l,r+1): #循环遍历\n",
    "                coins=nums[l-1]*nums[i]*nums[r+1]  #计算当前硬币数量\n",
    "                coins += dfs(l,i-1)+dfs(i+1,r)  #计算戳破两边的气球硬币总数\n",
    "                dp[(l,r)]=max(dp[(l,r)],coins)  #更新最大硬币数量\n",
    "            return dp[(l,r)]\n",
    "        return dfs(1,len(nums)-2)  #减去两个虚拟气球"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCoins(self, nums: List[int]) -> int:\n",
    "        nums=[1]+nums+[1] #添加两个虚拟气球\n",
    "        dp={} #用于储存子问题的解\n",
    "        def dfs(l,r): #定义深度优先搜索函数\n",
    "            if l>r:\n",
    "                return 0\n",
    "            if (l,r)in dp:\n",
    "                return dp[(l,r)]\n",
    "            dp[(l,r)]=0\n",
    "            for i in range(l,r+1):\n",
    "                coins=nums[l-1]*nums[i]*nums[r+1] #计算戳破后的硬币数量\n",
    "                coins += dfs(l,i-1)+dfs(i+1,r) #递归计算戳破左右两边的气球获得的硬币数量\n",
    "                dp[(l,r)]=max (dp[(l,r)],coins) # 更新当前范围的最大硬币数\n",
    "            return dp[(l,r)]\n",
    "        return dfs(1,len(nums)-2) # 减去添加的两个虚拟气球"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
